/* 542. 01 矩阵 */
/**
 * @param {number[][]} mat
 * @return {number[][]}
 */

/* 
    暴力
    如果值为0,则距离的出为0
    如果元素值不为0,则对该元素进行bfs 找出最短距离
*/

var updateMatrix = function (matrix) {
	if (!matrix.length || !matrix[0].length) return null

	let n = matrix.length
	let m = matrix[0].length
	let ans = new Array(n)
	for (let i = 0; i < n; i++) ans[i] = new Array(m).fill(-1)

	for (let i = 0; i < n; i++)
		for (let j = 0; j < m; j++) {
			if (matrix[i][j] === 0) ans[i][j] = 0
			else ans[i][j] = bfs(i, j)
		}

	return ans

	function bfs(row, col) {
		let queue = [[row, col]]
		let visited = new Array(n)
		let dist = 0
		for (let i = 0; i < n; i++) visited[i] = new Array(m).fill(false)
		visited[row][col] = true
		while (queue.length) {
			let len = queue.length
			dist++
			for (let i = 0; i < len; i++) {
				let top = queue.shift()

				if (top[0] + 1 < n && !visited[top[0] + 1][top[1]]) {
					if (matrix[top[0] + 1][top[1]] === 0) return dist
					queue.push([top[0] + 1, top[1]])
					visited[top[0] + 1][top[1]] = true
				}
				if (top[0] - 1 >= 0 && !visited[top[0] - 1][top[1]]) {
					if (matrix[top[0] - 1][top[1]] === 0) return dist
					queue.push([top[0] - 1, top[1]])
					visited[top[0] - 1][top[1]] = true
				}
				if (top[1] + 1 < m && !visited[top[0]][top[1] + 1]) {
					if (matrix[top[0]][top[1] + 1] === 0) return dist
					queue.push([top[0], top[1] + 1])
					visited[top[0]][top[1] + 1] = true
				}
				if (top[1] - 1 >= 0 && !visited[top[0]][top[1] - 1]) {
					if (matrix[top[0]][top[1] - 1] === 0) return dist
					queue.push([top[0], top[1] - 1])
					visited[top[0]][top[1] - 1] = true
				}
			}
		}
	}
}

/* 
    多源BFS
    本体可以转化为对于所有值为0的点同时向外扩散（速度为1格/次）求当扩散到矩阵
    中所有点的时间
*/

var updateMatrix = function (mat) {
	const n = mat.length,
		m = mat[0].length
	const dp = new Array(n).fill(0).map(() => new Array(m).fill(-1))
	const queue = []
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (mat[i][j] === 0) {
				dp[i][j] = 0
				queue.push([i, j])
			}
		}
	}
	let dist = 0
	while (queue.length) {
		let len = queue.length
		dist++

		for (let i = 0; i < len; i++) {
			let top = queue.shift()

			if (top[0] + 1 < n && dp[top[0] + 1][top[1]] === -1) {
				queue.push([top[0] + 1, top[1]])
				dp[top[0] + 1][top[1]] = dist
			}
			if (top[0] - 1 >= 0 && dp[top[0] - 1][top[1]] === -1) {
				queue.push([top[0] - 1, top[1]])
				dp[top[0] - 1][top[1]] = dist
			}
			if (top[1] + 1 < m && dp[top[0]][top[1] + 1] === -1) {
				queue.push([top[0], top[1] + 1])
				dp[top[0]][top[1] + 1] = dist
			}
			if (top[1] - 1 >= 0 && dp[top[0]][top[1] - 1] === -1) {
				queue.push([top[0], top[1] - 1])
				dp[top[0]][top[1] - 1] = dist
			}
		}
	}
	return dp
}

var updateMatrix = function (matrix) {
	if (!matrix.length || !matrix[0].length) return null
	const n = matrix.length
	const m = matrix[0].length
	const ans = new Array(n)
	for (let i = 0; i < n; i++) ans[i] = new Array(m).fill(n + m)
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (matrix[i][j] === 0) ans[i][j] = 0
		}
	}
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (i >= 1) ans[i][j] = Math.min(ans[i][j], ans[i - 1][j] + 1)
			if (j >= 1) ans[i][j] = Math.min(ans[i][j], ans[i][j - 1] + 1)
		}
	}

	for (let i = n - 1; i >= 0; i--) {
		for (let j = 0; j < m; j++) {
			if (i < n - 1) ans[i][j] = Math.min(ans[i][j], ans[i + 1][j] + 1)
			if (j >= 1) ans[i][j] = Math.min(ans[i][j], ans[i][j - 1] + 1)
		}
	}

	for (let i = n - 1; i >= 0; i--) {
		for (let j = m - 1; j >= 0; j--) {
			if (i < n - 1) ans[i][j] = Math.min(ans[i][j], ans[i + 1][j] + 1)
			if (j < m - 1) ans[i][j] = Math.min(ans[i][j], ans[i][j + 1] + 1)
		}
	}
	for (let i = 0; i < n; i++) {
		for (let j = m - 1; j >= 0; j--) {
			if (i >= 1) ans[i][j] = Math.min(ans[i][j], ans[i - 1][j] + 1)
			if (j < m - 1) ans[i][j] = Math.min(ans[i][j], ans[i][j + 1] + 1)
		}
	}

	return ans
}
const res = updateMatrix([
	[0, 0, 0],
	[0, 1, 0],
	[1, 1, 1],
])

console.log('updateMatrix :>>', res)
